//
//  main.cpp
//  BubbleSort
//
//  Created by chenyh on 2021/2/22.
//

#include <iostream>
using namespace std;
/**
 
 冒泡排序(Bubble Sort)也叫做气泡排序法，是交换排序的一种，是根据在水中轻气 泡不能在重气泡之下的原则设计的。主要思想是:扫描所有数据，两两比较，发现违反轻 气泡在重气泡之下原则的数，交换其位置，让重气泡下沉，轻气泡上浮。
 冒泡排序分为下沉排序和上浮排序两种。下沉排序从上往下扫描数据，先将序列中的 第 1 个元素与第 2 个元素进行比较，如果前者大于后者，则交换两者的位置，否则不交换; 然后将第 2 个元素与第 3 个元素进行比较，如果前者大于后者，则交换两者位置，否则不 交换;依次进行此过程，直到第 n–1 个元素与第 n 个元素比较为止。这一过程被称为一趟 排序。经过第一趟排序，“下沉排序”将最大的元素放置到了第 n 个位置上。然后对前 n–1 个元素进行同样过程，依次类推，直到某一趟排序不再出现交换行为为止，排序完成。上 浮排序的思想与此类似，但是过程相反。上浮排序从下往上扫描数据，第一趟排序将最小 的元素放置到第一个位置，然后对后 n–1 个元素进行重复的交换排序过程，直到某一趟排 序不再出现元素的位置交换为止，排序才算完成。由于这两种冒泡排序思想是一样的，只 是操作方式略有不同，所以这里我以下沉排序为例讲解冒泡排序算法，以后如果没有说明， 本章的冒泡排序均指下沉排序方式。
 冒泡排序算法的每一趟排序中，相邻元素之间的比较动作是必 须完成的，但是元素之间是否交换位置则要视情况而定，只有上面的元素大于下面的元素， 元素之间才需要交换位置。如果某一趟排序只有比较动作而没有元素位置交换动作，则说 明我们现在遍历的是一个已经排好序的数据集，说明冒泡排序完成。由此可知，冒泡排序 的执行总趟数与元素个数 n 没有必然联系，这一点与我们前面介绍的插入排序算法是有区 别的，请读者注意。
 5.2.2 算法实现
 第5章 排序算法
    图 5-4 冒泡排序执行过程
 从上面的介绍我们已经知道，冒泡排序算法是一种交换排序算法，它的主要步骤分为 两步:相邻元素的比较和元素位置的交换。通过我们的分析发现，冒泡排序终止的标志是 在某一趟排序过程中只有比较动作而没有交换动作。那么，为了确定某一趟排序过程中是 否发生了交换动作，设置一个标志量 flag，并约定 flag=1 时，表示本趟排序中有元素交换 动作;flag=0 时，表示本趟排序没有交换动作。
 我们在每趟排序开始之前，先将 flag 置为 0，在排序过程中，如果出现元素位置交换， flag 置为 1，否则就保持 0 值。冒泡排序最多进行 n–1 趟排序(元素倒序排列时)，最少 要进行一趟排序(元素按顺序有序排列时)。冒泡排序的算法描述如下:
 */
template <typename DataType>
void swap(DataType *a,DataType *b) {
    DataType temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
/**冒泡排序*/
template <typename DataType>
void bubbleSort(DataType data[],int n) {
    int flag;           //设置交换标志
    int i=1,j;
    do {
        flag = 0;
        for (j = 0; j+1<n; j++) {
            if (data[j] > data[j+1]) {
                swap(data[j], data[j+1]);
                flag = 1;   //将标志值改为1，表明本躺排序中发生了元素交换
            }
        }
        i++;
    } while (i < n && flag == 1); //当i<n且本躺排序进行了数据交换的时候才继续循环
}

/**
 上面代码中，swap()函数实现将两个元素的值进行交换。bubbleSort()函数是我们实现 算法的核心代码，在这里我们设置了 flag 变量，在每趟排序时都将该值设为 0，一旦本趟 排序时发生了元素交换，设该值为 1。有元素交换说明排序还没完成，还有元素需要排序， 否则排序完成。所以我们将控制排序趟数的循环条件，设置为趟数达到最大排序趟数之前 并且本趟排序进行了元素交换。只有在这种条件下，我们的排序才会继续进行。
 冒泡排序在最好的情况下，初始状态就已经是升序排列，则只需要经过一趟 n–1 次元 素之间的比较，且不用进行元素移动，就可结束排序，这时，冒泡排序的时间复杂度与元 素的个数呈线性关系，为 O(n)。在最坏情况下，当参加排序的数据元素为逆序排列时，或
 最小值元素在序列的最后时，需要进行 n–1 趟排序，每趟排序需要进行的比较动作次数为 n
 数列:n–1, n–2,...,1，所以总共进行(i 1) = n(n 1)/2次比较操作，冒泡排序的最坏时间 i=2
 复杂度为 O(n2)。在一般情况下，即数据随机分布的情况下，冒泡排序的时间复杂度也是 O(n2)。
 由于冒泡排序算法的元素交换是在相邻元素之间进行的，不会改变值相同的元素的相 对位置，因此，冒泡排序是一种稳定排序算法。
 */

/**
 【例 5-3】 有一个整数型数组{23,43,23,19,87,65,78,90,7,10}，实现一个 C++程序，用冒 泡排序算法对该数组排序，并输出结果。
 【分析】该例是冒泡排序的基本题型，主要是考察我们对冒泡排序算法的理解。
 */

/**
 交换函数
 */
void swap1(int *a,int *b)
{
    //根据a = a^b^b 利用按位异或《参加运算的两个数，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。》与运算交换两树的值，省去中间变量
    *a = *a^*b;
    *b = *a^*b;
    *a = *a^*b;
}

void bubbleSortI(int data[],int n )
{
    
    int flag; int i=1,j;
    do
    {
        flag = 0;
        for(j = 0;j+1<n;j++) {
            if(data[j]>data[j+1]){
                 swap(data[j],data[j+1]);
                  flag = 1; }
            
        }
        i++;
    }while(i<n && flag == 1);
    
    
}

/**
 例 5-4】 按从大到小的顺序排序{25,30,16,87,89,102,1,23}并输出结果。
 【分析】该例要求按从大到小的顺序排列元素，这样就需要我们对上面的排序算法做 一些改动。要实现从大到小的排列，我们发现只需要在进行元素比较的时候，进行与上述 讲解相反的操作，即发现前项小于后项者，交换其值;前项大于后项者，不进行交换。
 */
template <typename DataType>
void bubbleSort2(DataType data[],int n) {
    int flag = 1;
    int i=n,j=0;
    DataType temp;
    while (i > 0 && flag == 1) {
        flag = 0;
        for (j=0; j+1<i; j++) {
            if (data[j]<data[j+1]) {
                //将值较大的元素往前移，实现从大到小的排序
                temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
                flag=1;
            }
        }
        i--;
    }
}
void bubbleSort2I(int data[],int n)
{
    int i,j;
    for (i=0; i<n; i++) {
        for (j=0; j<n-1; j++) {
            if (data[j] < data[j+1]) {
                swap1(&data[j], &data[j+1]);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
   
    int data[10] = {23,43,23,19,87,65,78,90,7,10}; cout<<"排序前的数组为:"<<endl;
    for(int i = 0;i<10;i++)
        cout<<data[i]<<" ";
    cout<<endl;
    bubbleSort2I(data,10);
    cout<<"排序后的数组为:"<<endl;
    for(int i = 0;i<10;i++)
        cout<<data[i]<<" ";
    cout<<endl;
    return 0;
}
